This invention concerns a method of providing a position code claim 1. The invention also concerns a method of calculating a position claim 18. The invention also concerns computer program products, a device for position determination and a product with a position code.
In many situations it is desirable to be able to determine an absolute position on a surface. One example concerns the digitization of drawings. Another is when an electronic version of handwritten information is required.
U.S. Pat. No. 5,852,434 describes a device for determining an absolute position. The device comprises a writing surface which is provided with a position-coding pattern by means of which X-Y-coordinates can be determined, a detector which can detect the position-coding pattern and a processor which, on the basis of the detected position-coding pattern, can determine the position of the detector relative to the writing surface. The device makes it possible for a user to enter handwritten and hand-drawn information into a computer at the same time as the information is being written/drawn on the writing surface.
Three examples of position coding are given in U.S. Pat. No. 5,852,434. The first example is symbols, each of which is constructed of three concentric circles. The outer circle represents the X-coordinate and the middle circle the Y-coordinate. Both the outer circles are additionally divided into 16 parts which, depending upon whether they are filled in or not, indicate different numbers. This means that each pair of coordinates X, Y is coded by a complex symbol with a particular appearance.
In the second example the coordinates of each point on the writing surface are given by means of bar-codes, a bar-code for the X-coordinate being shown above a bar-code for the Y-coordinate.
A checkered pattern which can be used to code the X- and Y-coordinates is given as a third example. However, there is no explanation as to how the checkered pattern is constructed or how it can be converted into coordinates.
A problem with the known pattern is that it is constructed of complex symbols and the smaller these symbols are made, the more difficult it is to produce the patterned writing surface and the greater the risk of incorrect position determinations, while the larger the symbols are made, the poorer the position resolution becomes.
A further problem is that the processing of the detected position-coding pattern becomes rather complicated, due to the fact that a processor has to interpret complex symbols.
An additional problem is that the detector must be constructed in such a way that it can record four symbols at the same time so that it is certain to cover at least one symbol in its entirety, which is necessary in order for the position determination to be able to be carried out. The ratio between the required sensor surface and the surface of the position-coding pattern which defines a position is thus large.
Appendix A to WO 92/17859 gives the following example of how the pattern can be constructed and how a position can be decoded.
Take the following m-sequences: s=(0,0,1,0,1,1,1) and t=(0,1,1). Build up a position-coding pattern by letting a first column in the pattern be equal to the sequence s. In order to build up the following columns, look at the t-sequence. If the first element in the t-sequence is 0 then the second column consists of the s-sequence. If the first element is 1 instead, then the second column consists of the s-sequence cyclic-shifted by one step. Subsequent columns are built up in a corresponding way in accordance with the values of the elements in the t-sequence. The following pattern is then obtained:
Assume now that one wants to find the position of a partial surface with the subset of the pattern shown below.
The first column in the subset is (1,0,1). This subsequence appears in position 2 in the s-sequence. The cyclic shifts in the subset are (1,1). This sub-sequence appears in position 1 in the t-sequence. The accumulated shifts in the pattern is (0,0,1,2) and therefore the vertical position of the subset is 2+0=2. The position of the subset on the partial surface is thus (1,2).
With this pattern the above-mentioned problems with complex symbols are avoided and the ratio is reduced between the required sensor surface and the surface of the position-coding pattern which defines a position.
An interesting characteristic of a position-coding pattern of this type is, however, the ability to code a large pattern with many unique positions so that position determination can be carried out on as large a surface as possible. In the example described above, the size in the vertical direction is limited by the length of the s-sequence and the size in the horizontal direction by the length of the t-sequence. The length of these sequences can, however, not be increased without limit as the sequences should have the characteristic that if a sub-sequence of k bits is taken, this sub-sequence should only occur in one position in the sequence. An increase in the length of the sequence can thus imply an increase in the length of the sub-sequence and thereby an increase of the partial surface which must be recorded in order to be able to determine a position.
An object of this invention is to show how a position code which makes possible coding of a large number of positions can be provided.
According to a first aspect, the invention concerns more particularly a method of providing a position code on a surface, which position code codes a plurality of positions in a first direction on the surface, comprising the steps of using a first cyclic number series, which has the characteristic that the position in the number series of each number sequence of a first predetermined length is determined unambiguously; printing out the first cyclic number series a plurality of times across the surface, different rotations of the first cyclic number series being used so that predetermined displacements arise between adjacent number series.
The method is characterized in that the step of printing out comprises dividing the surface into a plurality of first code windows in the first direction, each of which comprises at least three first cyclic number series and has one number series overlapping one number series of adjacent first code windows, and using such rotations of the first cyclic number series when printing this out that the position of each first code window in the first direction is coded by means of the displacements between the first cyclic number series belonging to the code window.
This differs from prior-art in that the position code is divided into a plurality of code windows, the respective position of which is coded by the size of the displacements between the cyclic number series which belong to the code window. The code windows are so arranged that no displacement belongs to more than one code window. The coding in the first direction is thus no longer based on displacements which follow a cyclic number series and consequently avoids the restrictions which this implies.
The above-mentioned displacements can in practice be determined as the difference between the corresponding number sequences in the number series.
One rotation of the cyclic number series can also be referred to as a cyclic-shifted version of the number series. Different rotations thus start at different places in the number series.
As will be explained later, the printout of the cyclic number series does not need to be carried out with numbers in explicit form, but the numbers can preferably be printed out using graphic symbols which are easier to recognize, for example by image processing of the position code.
In a preferred embodiment, such rotations of the cyclic number series are used that at least some of the displacements are greater than one. As a result, a much greater number of positions can be coded in the first direction than if only displacements with one step had been used.
In a preferred embodiment, in addition such rotations of the first cyclic number series are used that the displacements of each code window define a position number in mixed base which indicates the position of the first code window in the first direction and in addition the least significant displacement is indicated in the position number.
The position number can be n-adic, where n is the number of first cyclic number series within a code window minus one.
The indication of the least significant displacement in the position number makes it possible to determine the position of partial surfaces which are the same size as the code windows but which do not coincide with any of these but partly overlap two code windows in the first direction.
The least significant displacement can be indicated in various ways. One way comprises using such rotations of the first cyclic number series that the least significant displacement is less than other displacements. Another way comprises using such rotations of the first cyclic number series that the least significant displacement lies within a first size range and other displacements lie within a second size range. The first way gives the ability to code more positions.
In a preferred embodiment, the method further comprises the step of creating different variants of the position code by letting the first cyclic number series in the first direction, that is the cyclic number series from which the first displacement is calculated, start in different positions for different variants.
As a result, the maximum number of codable positions is further increased. The number of possible variants is equal to the number of numbers in the first cyclic number series.
In a preferred embodiment, the position code also codes a plurality of positions in a second direction on the surface and the method comprises for this purpose the steps of using a second cyclic number series, which has the characteristic that the position in the number series of each number sequence of a second predetermined length is determined unambiguously, printing out the second cyclic number series across the surface a plurality of times, different rotations of the second cyclic number series being used so that the second cyclic number series start at different start positions, the step of printing out comprises dividing the surface into a plurality of non-overlapping second code windows, each of which comprises a predetermined plurality of second cyclic number series and using such rotations of the second cyclic number series that the position of each second code window in the second direction is coded by means of the start positions of the associated second cyclic number series.
The coding in the second direction is based on the same principle as the coding in the first direction, namely on the use of code windows with the associated advantages. However, here the start positions for the second cyclic number series are used instead of the displacements, which gives the possibility of more positions. This is based, however, on the position in the first direction being known.
The method of coding positions in the second direction can be used together with methods of coding positions in the first direction other than the method according to the invention.
The position in the second direction can be coded by a position number in mixed base and the least significant start position can be indicated similarly to the code windows in the first direction and with corresponding advantages.
In a preferred embodiment, the second cyclic number series is identical to the first cyclic number series, which is preferably binary. This is advantageous in connection with the decoding as it is sufficient to store a table with positions corresponding to the number sequences. In addition, the first and the second code windows can be the same size and can overlap each other.
A simple position code for positions in a Cartesian coordinate system is obtained if the first cyclic number series is printed out in columns across the surface and the second cyclic number series is printed out in rows across the surface or vice versa. The numbers in the number series can be printed out once in each row/column or several times in succession. The same rotation of the number series is then used throughout the same row/column.
In a preferred embodiment, the printing out of the first and the second cyclic number series is carried out in such a way that each intersection between raster lines in a raster which covers the surface is allocated a number from the first cyclic number sequence and a number from the second cyclic number sequence and the numbers belonging to each intersection are coded graphically by a mark on the surface at the intersection. The raster can be printed out on the surface, but is preferably virtual.
At each intersection there is thus a number which belongs to the position coding for the first direction and a number which belongs to the position coding for the second direction. These numbers can be separated when decoding, but they can be coded by a common mark on the surface. This makes possible a high resolution and a high density of information.
The intersections can also be called raster points.
In a preferred embodiment, the various possible combinations of numbers from the first and the second cyclic number series are coded by different locations of the mark relative to the intersection.
If both the number series are bit series, four different possible number combinations are obtained (0,0; 1,0; 0,1; and 1,1). These are coded by four different locations of the mark. The different locations can be a predetermined displacement from the intersection along the four different raster lines which extend from this. The intersection can be regarded as a nominal position, relative to which the mark is displaced.
The use of marks which represent different values dependent upon their location has many advantages. Among other things, all marks can have the same appearance, which facilitates the arranging of the position code on a surface.
The numbers which are allocated to the intersections can naturally be represented graphically in other ways than by means of a displaced mark. Instead, four marks with different appearances can be used, or a mark for each of the numbers.
The method described above can be implemented in a computer program, in an ASIC (Application Specific Integrated Circuit) or an FPGA (Field Programmable Gate Array) or in some other suitable way.
Another object of the invention is to provide a method of determining a position, which method is suitable to be used together with a position code of the type which is described above.
According to a second aspect, the invention thus concerns a method of calculating a position, in a first direction, for an arbitrary partial surface of a predetermined size on a surface which is provided with a position code, which for the position coding in the first direction is based on a first cyclic number series, which has the characteristic that the position in the number series of each first number sequence of a first predetermined length is determined unambiguously and which is printed out a plurality of times on the surface with different rotations so that adjacent first cyclic number series are displaced relative to each other by predetermined displacements, comprising the steps of identifying a plurality of first number sequences from the position code on the partial surface, determining the position of each first number sequence in the first cyclic number series, determining on the basis of these positions the displacements between the adjacent first cyclic number series containing the first number sequences from the partial surface. The method is characterized by the steps of determining from the displacements a position in the first direction of a first code window, which the said partial surface at least partly overlaps, which first code window is one of a plurality of code windows in the first direction, each of which comprises a predetermined plurality of first cyclic number series and has one number series overlapping one number series of adjacent first code windows.
This method is advantageous as it makes possible position determination on a surface which has a position code which codes a large number of positions.
The method can be implemented in a computer program, in an ASIC or an FPGA or in some other suitable way.
The method of determining a position can be implemented with additional steps which are adapted to decode different implementations of the position-coding pattern which is obtained as a result of the method of providing a position code described above. These steps are also described in greater detail in the specific descriptive section.
A further object of this invention is to provide a device for position determination which is suitable to use for decoding a position-coding pattern of the type described above.
According to a third aspect, the invention thus concerns a device for position determination, comprising a sensor for producing an image of a partial surface of a surface which is provided with a position code, and image processing means, which are arranged to calculate based on the subset of the position code which is present in the image of the partial surface.
A further object of the invention is to provide a product with a position-coding pattern which makes possible coding of a large number of positions.
According to a fourth aspect, the invention thus concerns a product which makes possible determination of a position in a first direction for an arbitrary partial surface of a predetermined size on a surface of the product which is provided with a position code, which for the position coding in the first direction is based on a first cyclic number series, which has the characteristic that the position in the number series of each first number sequence of a first predetermined length is determined unambiguously and which is printed out a plurality of times on the surface with different rotations so that adjacent first cyclic number series are displaced relative to each other by predetermined displacements, a plurality of first number sequences from the position code being identifiable on the partial surface, in order to determine the position of each first number sequence in the first cyclic number series, and the displacements between the adjacent first cyclic number series containing the first number sequences from the partial surface being determinable on the basis of these positions. The product is characterized in that a position in the first direction of a first code window which said partial surface at least partly overlaps is determinable from the displacements, which first code window is one of a plurality of code windows in the first direction, each of which comprises a predetermined plurality of first cyclic number series and has one number series overlapping one number series of adjacent first code windows.
The advantages of the product are apparent from the discussion above. The features which are described in connection with the methods of providing a position code and determining a position are naturally also applicable to the product.